package sort

//一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
//
//从第一个元素开始，该元素可以认为已经被排序；
//取出下一个元素，在已经排序的元素序列中从后向前扫描；
//如果该元素（已排序）大于新元素，将该元素移到下一位置；
//重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
//将新元素插入到该位置后；
//重复步骤2~5。

// 插入排序
type InsertionSort struct {
}

func (i *InsertionSort) Sort(nums []int) {

	l := len(nums)
	sortedIndex := 0

	for i := 1; i < l; i++ {
		n := nums[i]
		sortedIndex = i
		for j := sortedIndex; j > 0; j-- {

			if nums[j] < n {
				break
			}

			if nums[j] > n {
				Swap(nums, j, j+1)
			}

		}

	}
}
